题意
在$n$个柱子上依次放入$1…ans$的球，使得每根柱子的球上大下小，且所有相邻的球相加为完全平方数
求最大的$ans$
题解
把每一根柱子看成一条路径，相加为平方数则连边
网络流最小路径覆盖问题，用给定的路径覆盖尽可能多的点
调试记录
r开得太小
整数二分l<=r
及时记录答案
以前写的输出方案是错的1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
const int maxn = 50005;
const int INF = 0x3f3f3f3f;
using namespace std;
struct E{
int to, nxt, f;
int from;
}e[maxn << 1];
int head[maxn], tot;
void addedge(int u, int v, int f){
e[++tot].to = v, e[tot].nxt = head[u], e[tot].f = f;
head[u] = tot; e[tot].from = u;
}
void ins(int u, int v, int f){
addedge(u, v, f); addedge(v, u, 0);
}
int dep[maxn]; int T = 5001;
bool bfs(){
queue <int> q; q.push(0);
memset(dep, 0, sizeof dep); dep[0] = 1;
while (!q.empty()){
int cur = q.front(); q.pop();
for (int i = head[cur]; i; i = e[i].nxt)
if (!dep[e[i].to] && e[i].f){
dep[e[i].to] = dep[cur] + 1;
q.push(e[i].to);
}
}
return dep[T];
}
int rec[maxn], upper[maxn], mid;
int dfs(int cur, int Max){
if (cur == T) return Max;
int flow = 0;
for (int i = head[cur]; i; i = e[i].nxt){
if (flow == Max) return flow;
if (dep[e[i].to] == dep[cur] + 1 && e[i].f){
int tmp = dfs(e[i].to, min(Max - flow, e[i].f));
e[i].f -= tmp;
e[i ^ 1].f += tmp;
flow += tmp;
if (e[i].to != T && cur <= mid) rec[cur] = e[i].to - mid;
}
}
return flow;
}
int maxflow;
void Dinic(){
while (bfs()){
while (int tmp = dfs(0, INF)) maxflow += tmp;
}
}
int n, ans = 0, last[maxn], cnt;
vector <int> v[maxn];
int main(){
scanf("%d", &n);
int l = 0, r = 2000;
while (l <= r){
mid = (l + r) >> 1;
memset(e, 0, sizeof e); tot = 1; maxflow = 0;
memset(head, 0, sizeof head); memset(rec, 0, sizeof rec);
for (int i = 1; i <= mid; i++) ins(0, i, 1), ins(i + mid, T, 1), last[i] = tot - 1;
for (int i = 1; i <= mid; i++)
for (int j = i + 1; j <= mid; j++){
int tmp = i + j;
if ((int)sqrt(tmp) * (int)sqrt(tmp) == tmp) ins(i, j + mid, 1);
}
Dinic();
if (mid - maxflow <= n){
l = mid + 1;
if (ans < mid){
ans = mid; for (int i = 1; i <= cnt; i++) v[i].clear(); cnt = 0;
bool vis[maxn]; memset(vis, 0, sizeof vis);
for (int i = 1; i <= ans; i++){
if (vis[i] || e[last[i]].f == 0) continue;
int cur = i; ++cnt;
while (1){
v[cnt].push_back(cur); vis[cur] = 1; bool f = 0;
for (int j = head[cur]; j; j = e[j].nxt)
if (e[j].f == 0 && e[j].to != 0){
f = 1, cur = e[j].to - ans;
break;
}
if (!f) break;
}
}
}
}
else r = mid - 1;
}
printf("%d\n", ans);
for (int i = 1; i <= cnt; i++){
for (int j = 0; j < v[i].size(); j++)
printf("%d ", v[i][j]);
puts("");
}
return 0;
}